package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No40
 * @description 组合总和 II
 * @date 2021/3/3 上午11:49
 */
public class No40 {
    public static void main(String[] args) {
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        List<List<Integer>> res = combinationSum2(candidates,target);
        for (int i = 0; i < res.size(); i++) {
            List<Integer> temp = res.get(i);
            for (int j = 0; j < temp.size(); j++) {
                System.out.print(temp.get(j));
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return res;
        }
        Arrays.sort(candidates);
        boolean[] isUsed = new boolean[candidates.length];
        subCombinationSum2(candidates,target,0,isUsed,new ArrayList<Integer>(),res);
        return res;
    }

    private static void subCombinationSum2(int[] candidates, int target, int i, boolean[] isUsed, List<Integer> list, List<List<Integer>> res) {

        if(target == 0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j < candidates.length; j++) {
            if(j > 0 && candidates[j] == candidates[j - 1] && !isUsed[j - 1]){
                continue;
            }
            if(candidates[j] <= target){
                list.add(candidates[j]);
                isUsed[j] = true;
                subCombinationSum2(candidates,target - candidates[j],j + 1,isUsed,list,res);
                isUsed[j] = false;
                list.remove(list.size() - 1);
            }
        }
    }

}
